home *** CD-ROM | disk | FTP | other *** search
/ PsL Monthly 1993 December / PSL Monthly Shareware CD-ROM (December 1993).iso / prgmming / dos / c / tagsgen.exe / SORT.C < prev    next >
C/C++ Source or Header  |  1991-10-02  |  50KB  |  1,827 lines
  1. /* sort.c - sort lines of text (with all kinds of options).
  2.    Copyright 1989 Free Software Foundation
  3.                   Written December 1988 by Mike Haertel.
  4.  
  5.    This program is free software; you can redistribute it and/or modify
  6.    it under the terms of the GNU General Public License as published by
  7.    the Free Software Foundation; either version 1, or (at your option)
  8.    any later version.
  9.  
  10.    This program is distributed in the hope that it will be useful,
  11.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13.    GNU General Public License for more details.
  14.  
  15.    You should have received a copy of the GNU General Public License
  16.    along with this program; if not, write to the Free Software
  17.    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  18.  
  19.    The author may be reached (Email) at the address mike@ai.mit.edu,
  20.    or (US mail) as Mike Haertel c/o Free Software Foundation. */
  21.  
  22. /* MS-DOS port (c) 1990 by Thorsten Ohl, td12@ddagsi3.bitnet
  23.    This port is also distributed under the terms of the
  24.    GNU General Public License as published by the
  25.    Free Software Foundation.
  26.  
  27.    $Header: e:/gnu/sort/RCS/sort.c'v 0.3.0.4 90/08/26 19:03:05 tho Exp $
  28.  */
  29.  
  30. static char version[] = "GNU sort, version 0.3";
  31.  
  32. #include "std.h"
  33.  
  34. #ifndef MSDOS
  35. #include "unix.h"
  36. #endif /* not MSDOS */
  37.  
  38. #ifdef SORT_MODULE
  39. #include "sort.h"
  40. #endif
  41.  
  42. #include <errno.h>
  43. #include <signal.h>
  44. #include <stdio.h>
  45. #include <string.h>
  46.  
  47. #ifdef MSDOS
  48. #include <process.h>
  49. static void cleanup (void);
  50. static void assert_lines (int lines);
  51. void *xmalloc (unsigned int size);
  52. void *xrealloc (void *ptr, unsigned int size);
  53. static FILE *xfopen (char *file, char *how);
  54. static void xfclose (FILE *fp);
  55. static void xfwrite (char *buf, int size, int nelem, FILE *fp);
  56. static char *tempname (void);
  57. static void zaptemp (char *name);
  58. static void inittables (void);
  59. static void initbuf (struct buffer *buf, int alloc);
  60. static int fillbuf (struct buffer *buf, FILE *fp);
  61. static void initlines (struct lines *lines, int alloc);
  62. static char *begfield (struct line *line, struct keyfield *key);
  63. static char *limfield (struct line *line, struct keyfield *key);
  64. static void findlines (struct buffer *buf, struct lines *lines);
  65. static int fraccompare (char *a, char *b);
  66. static int numcompare (char *a, char *b);
  67. static int getmonth (char *s, int len);
  68. static int keycompare (struct line *a, struct line *b);
  69. static int compare (struct line *a, struct line *b);
  70. static int checkfp (FILE *fp);
  71. static void mergefps (FILE **fps, int nfps, FILE *ofp);
  72. static void sortlines (struct line *lines, int nlines, struct line *temp);
  73. static int check (char **files, int nfiles);
  74. static void merge (char **files, int nfiles, FILE *ofp);
  75. static void sort (char **files, int nfiles, FILE *ofp);
  76. static void insertkey (struct keyfield *key);
  77. static void usage (void);
  78. static void badfieldspec (char *s);
  79. static void inthandler (void);
  80. #ifndef SORT_MODULE
  81. int main (int argc, char **argv);
  82. #endif
  83. #endif /* MSDOS */
  84.  
  85. /* A few useful macros. */
  86. #define ISBLANK(c) ((c) == ' ' || (c) == '\t')
  87. #define MIN(a, b) ((a) < (b) ? (a) : (b))
  88. #define UCHAR_LIM (UCHAR_MAX + 1)
  89. #define UCHAR(c) ((unsigned char) (c))
  90.  
  91. /* Table of digits. */
  92. static int digits[UCHAR_LIM];
  93.  
  94. /* Table of white space. */
  95. static int blanks[UCHAR_LIM];
  96.  
  97. /* Table of non-printing characters. */
  98. static int nonprinting[UCHAR_LIM];
  99.  
  100. /* Table of non-dictionary characters (not letters, digits, or blanks). */
  101. static int nondictionary[UCHAR_LIM];
  102.  
  103. /* Translation table folding upper case to lower. */
  104. static char fold_tolower[UCHAR_LIM];
  105.  
  106. /* Table mapping 3-letter month names to integers.
  107.    Alphabetic order allows binary search. */
  108. static struct month {
  109.   char *name;
  110.   int val;
  111. } monthtab[] = {
  112.   "apr", 4,
  113.   "aug", 8,
  114.   "dec", 12,
  115.   "feb", 2,
  116.   "jan", 1,
  117.   "jul", 7,
  118.   "jun", 6,
  119.   "mar", 3,
  120.   "may", 5,
  121.   "nov", 11,
  122.   "oct", 10,
  123.   "sep", 9
  124. };
  125.  
  126. /* During the merge phase, the number of files to merge at once. */
  127. #ifdef MSDOS
  128. /* 14 (= 20 - 5 - 1) is a hard upper limit for MeSsy DOS versions <3.2
  129.    (and a soft one for later versions...) */
  130. #define NMERGE 12
  131. #else /* not MSDOS */
  132. #define NMERGE 16
  133. #endif /* not MSDOS */
  134.  
  135. /* Initial buffer size for in core sorting.  Will not grow unless a
  136.    line longer than this is seen. */
  137. #ifdef MSDOS
  138. static int sortalloc = 32767;
  139. #else /* not MSDOS */
  140. static int sortalloc = 524288;
  141. #endif /* not MSDOS */
  142.  
  143. /* Initial buffer size for in core merge buffers.  Bear in mind that
  144.    up to NMERGE * mergealloc bytes may be allocated for merge buffers. */
  145. static int mergealloc = 16384;
  146.  
  147. /* Guess of average line length. */
  148. static int linelength = 30;
  149.  
  150. /* Prefix for temporary file names. */
  151. #ifdef MSDOS
  152. static char *prefix;
  153. #else /* not MSDOS */
  154. static char *prefix = "/tmp";
  155. #endif /* not MSDOS */
  156.  
  157. /* Flag to reverse the order of all comparisons. */
  158. static int reverse;
  159.  
  160. /* Tab character separating fields.  If NUL, then fields are separated
  161.    by the empty string between a non-whitespace character and a whitespace
  162.    character. */
  163. static char tab;
  164.  
  165. /* Flag to remove consecutive duplicate lines from the output.
  166.    Only the last of a sequence of equal lines will be output. */
  167. static int unique;
  168.  
  169. /* Lines are held in core as counted strings. */
  170. struct line
  171. {
  172.   char *text;                   /* Text of the line. */
  173.   int length;                   /* Length not including final newline. */
  174.   char *keybeg;                 /* Start of first key. */
  175.   char *keylim;                 /* Limit of first key. */
  176. };
  177.  
  178. #ifdef MSDOS
  179. /* Using _huge line arrays under MS-DOS is terribly inefficient, so we
  180.    impose an upper limit on the number of lines cosidered at once.  The
  181.    user can break the input into digestable pieces by using the `-S' option
  182.    to adjust the input buffer size.
  183.    This only matters for files with very short lines ( < 8 chars).  */
  184. static int maxlines
  185.   = (int) (((1L << 16) - 1L) / sizeof (struct line));
  186.  
  187. void
  188. assert_lines (int lines)
  189. {
  190.   if (lines >= maxlines)
  191.     {
  192.       fprintf (stderr,
  193.                "sort: the number of lines per input buffer is restricted in\n"
  194.                "      the MS-DOS version.  For files with short lines, use\n"
  195.                "      the `-S <num>' option to reduce the buffer size.\n");
  196.       cleanup ();
  197. #ifdef SORT_MODULE
  198.       external_cleanup();
  199. #endif
  200.       exit (-1);
  201.     }
  202. }
  203. #endif /* MSDOS */
  204.  
  205. /* Arrays of lines. */
  206. struct lines
  207. {
  208.   struct line *lines;           /* Dynamically allocated array of lines. */
  209.   int used;                     /* Number of slots used. */
  210.   int alloc;                    /* Number of slots allocated. */
  211. };
  212.  
  213. /* Input buffers. */
  214. struct buffer
  215. {
  216.   char *buf;                    /* Dynamically allocated buffer. */
  217.   int used;                     /* Number of bytes used. */
  218.   int alloc;                    /* Number of bytes allocated. */
  219.   int left;                     /* Number of bytes left after line parsing. */
  220. };
  221.  
  222. /* Lists of key field comparisons to be tried. */
  223. static struct keyfield
  224. {
  225.   int sword;                    /* Zero-origin 'word' to start at. */
  226.   int schar;                    /* Additional characters to skip. */
  227.   int skipsblanks;              /* Skip leading white space at start. */
  228.   int eword;                    /* Zero-origin first word after field. */
  229.   int echar;                    /* Additional characters in field. */
  230.   int skipeblanks;              /* Skip trailing white space at finish. */
  231.   int *ignore;                  /* Boolean array of characters to ignore. */
  232.   char *translate;              /* Translation applied to characters. */
  233.   int numeric;                  /* Flag for numeric comparison. */
  234.   int month;                    /* Flag for comparison by month name. */
  235.   int reverse;                  /* Reverse the sense of comparison. */
  236.   struct keyfield *next;        /* Next keyfield to try. */
  237. } keyhead;
  238.  
  239. /* The list of temporary files. */
  240. static struct tempnode
  241. {
  242.